package backtrackStudy;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class LetterCombinations {

    private static List<String> res = new LinkedList<>();

    /**
     * LeetCode T17 电话号码的字母组合
     * 组合问题，前面两题中，给定的每一层的元素都在同一个集合，该题不在同一个集合
     *
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     *
     * @param args
     */
    public static void main(String[] args) {

    }

    public static List<String> letterCombinations(String digital){
        if (digital == null || digital.length() < 1){
            return res;
        }
        //使用哈希表存储数字和字符的映射
        HashMap<Character, String> phoneMap = new HashMap<Character, String>(){
            {
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }
        };
        //存放路径
        StringBuilder trace = new StringBuilder();
        backtrace(digital, 0, phoneMap, trace);
        return res;
    }

    /**
     *
     * @param digital 需要转化的数字字符串
     * @param beginIndex 索引位置
     * @param phoneMap 数字和字符的映射
     * @param trace 存放回溯路径
     */
    public static void backtrace(String digital, int beginIndex, HashMap<Character, String> phoneMap, StringBuilder trace){
        //定义出口
        if (digital.length() == beginIndex){
            res.add(trace.toString());
            return;
        }
        //获得需要遍历的字符串
        char c = digital.charAt(beginIndex);
        String s = phoneMap.get(c);
        for (int i = 0; i < s.length(); i++){
            //选择
            trace.append(s.charAt(i));
            //递归下一个数字
            backtrace(digital, beginIndex + 1, phoneMap, trace);
            //取消
            trace.deleteCharAt(trace.length()-1);
        }
    }
}
